; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -aggressive-instcombine -S | FileCheck %s

define i16 @shl_1(i8 %x) {
; CHECK-LABEL: @shl_1(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[ZEXT]], 1
; CHECK-NEXT:    ret i16 [[SHL]]
;
  %zext = zext i8 %x to i32
  %shl = shl i32 %zext, 1
  %trunc = trunc i32 %shl to i16
  ret i16 %trunc
}

define i16 @shl_15(i8 %x) {
; CHECK-LABEL: @shl_15(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[ZEXT]], 15
; CHECK-NEXT:    ret i16 [[SHL]]
;
  %zext = zext i8 %x to i32
  %shl = shl i32 %zext, 15
  %trunc = trunc i32 %shl to i16
  ret i16 %trunc
}

; Negative test - shift amount isn't less than target bitwidth

define i16 @shl_16(i8 %x) {
; CHECK-LABEL: @shl_16(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[ZEXT]], 16
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[SHL]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i8 %x to i32
  %shl = shl i32 %zext, 16
  %trunc = trunc i32 %shl to i16
  ret i16 %trunc
}

; Negative test -- variable shift amount

define i16 @shl_var_shift_amount(i8 %x, i8 %y) {
; CHECK-LABEL: @shl_var_shift_amount(
; CHECK-NEXT:    [[ZEXT_X:%.*]] = zext i8 [[X:%.*]] to i32
; CHECK-NEXT:    [[ZEXT_Y:%.*]] = zext i8 [[Y:%.*]] to i32
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[ZEXT_X]], [[ZEXT_Y]]
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[SHL]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext.x = zext i8 %x to i32
  %zext.y = zext i8 %y to i32
  %shl = shl i32 %zext.x, %zext.y
  %trunc = trunc i32 %shl to i16
  ret i16 %trunc
}

define i16 @shl_var_bounded_shift_amount(i8 %x, i8 %y) {
; CHECK-LABEL: @shl_var_bounded_shift_amount(
; CHECK-NEXT:    [[ZEXT_X:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[ZEXT_Y:%.*]] = zext i8 [[Y:%.*]] to i16
; CHECK-NEXT:    [[AND:%.*]] = and i16 [[ZEXT_Y]], 15
; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[ZEXT_X]], [[AND]]
; CHECK-NEXT:    ret i16 [[SHL]]
;
  %zext.x = zext i8 %x to i32
  %zext.y = zext i8 %y to i32
  %and = and i32 %zext.y, 15
  %shl = shl i32 %zext.x, %and
  %trunc = trunc i32 %shl to i16
  ret i16 %trunc
}

; Negative test (https://reviews.llvm.org/D108091#2950930)

define i32 @shl_check_no_overflow(i32 %call62, i16 %call63) {
; CHECK-LABEL: @shl_check_no_overflow(
; CHECK-NEXT:    [[CONV64142:%.*]] = zext i32 [[CALL62:%.*]] to i64
; CHECK-NEXT:    [[CONV65:%.*]] = sext i16 [[CALL63:%.*]] to i64
; CHECK-NEXT:    [[SH_PROM66:%.*]] = and i64 [[CONV65]], 4294967295
; CHECK-NEXT:    [[SHL67:%.*]] = shl i64 [[CONV64142]], [[SH_PROM66]]
; CHECK-NEXT:    [[CONV68:%.*]] = trunc i64 [[SHL67]] to i32
; CHECK-NEXT:    ret i32 [[CONV68]]
;
  %conv64142 = zext i32 %call62 to i64
  %conv65 = sext i16 %call63 to i64
  %sh_prom66 = and i64 %conv65, 4294967295
  %shl67 = shl i64 %conv64142, %sh_prom66
  %conv68 = trunc i64 %shl67 to i32
  ret i32 %conv68
}

define i16 @shl_smaller_bitwidth(i8 %x) {
; CHECK-LABEL: @shl_smaller_bitwidth(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[ZEXT]], 1
; CHECK-NEXT:    [[AND:%.*]] = and i16 [[SHL]], 42
; CHECK-NEXT:    ret i16 [[AND]]
;
  %zext = zext i8 %x to i16
  %shl = shl i16 %zext, 1
  %zext2 = zext i16 %shl to i32
  %and = and i32 %zext2, 42
  %trunc = trunc i32 %and to i16
  ret i16 %trunc
}

define i16 @shl_larger_bitwidth(i8 %x) {
; CHECK-LABEL: @shl_larger_bitwidth(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[ZEXT]], 1
; CHECK-NEXT:    [[AND:%.*]] = and i16 [[SHL]], 42
; CHECK-NEXT:    ret i16 [[AND]]
;
  %zext = zext i8 %x to i64
  %shl = shl i64 %zext, 1
  %zext2 = trunc i64 %shl to i32
  %and = and i32 %zext2, 42
  %trunc = trunc i32 %and to i16
  ret i16 %trunc
}

define <2 x i16> @shl_vector(<2 x i8> %x) {
; CHECK-LABEL: @shl_vector(
; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
; CHECK-NEXT:    [[S:%.*]] = shl <2 x i16> [[Z]], <i16 4, i16 10>
; CHECK-NEXT:    ret <2 x i16> [[S]]
;
  %z = zext <2 x i8> %x to <2 x i32>
  %s = shl <2 x i32> %z, <i32 4, i32 10>
  %t = trunc <2 x i32> %s to <2 x i16>
  ret <2 x i16> %t
}

; Negative test - can only fold to <2 x i16>, requiring new vector type

define <2 x i8> @shl_vector_no_new_vector_type(<2 x i8> %x) {
; CHECK-LABEL: @shl_vector_no_new_vector_type(
; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[S:%.*]] = shl <2 x i32> [[Z]], <i32 4, i32 10>
; CHECK-NEXT:    [[T:%.*]] = trunc <2 x i32> [[S]] to <2 x i8>
; CHECK-NEXT:    ret <2 x i8> [[T]]
;
  %z = zext <2 x i8> %x to <2 x i32>
  %s = shl <2 x i32> %z, <i32 4, i32 10>
  %t = trunc <2 x i32> %s to <2 x i8>
  ret <2 x i8> %t
}

; Negative test

define <2 x i16> @shl_vector_large_shift_amount(<2 x i8> %x) {
; CHECK-LABEL: @shl_vector_large_shift_amount(
; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[S:%.*]] = shl <2 x i32> [[Z]], <i32 16, i32 5>
; CHECK-NEXT:    [[T:%.*]] = trunc <2 x i32> [[S]] to <2 x i16>
; CHECK-NEXT:    ret <2 x i16> [[T]]
;
  %z = zext <2 x i8> %x to <2 x i32>
  %s = shl <2 x i32> %z, <i32 16, i32 5>
  %t = trunc <2 x i32> %s to <2 x i16>
  ret <2 x i16> %t
}

define i16 @shl_nuw(i8 %x) {
; CHECK-LABEL: @shl_nuw(
; CHECK-NEXT:    [[Z:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[S:%.*]] = shl i16 [[Z]], 15
; CHECK-NEXT:    ret i16 [[S]]
;
  %z = zext i8 %x to i32
  %s = shl nuw i32 %z, 15
  %t = trunc i32 %s to i16
  ret i16 %t
}

define i16 @shl_nsw(i8 %x) {
; CHECK-LABEL: @shl_nsw(
; CHECK-NEXT:    [[Z:%.*]] = zext i8 [[X:%.*]] to i16
; CHECK-NEXT:    [[S:%.*]] = shl i16 [[Z]], 15
; CHECK-NEXT:    ret i16 [[S]]
;
  %z = zext i8 %x to i32
  %s = shl nsw i32 %z, 15
  %t = trunc i32 %s to i16
  ret i16 %t
}

define i16 @lshr_15(i16 %x) {
; CHECK-LABEL: @lshr_15(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ZEXT]], 15
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[LSHR]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i16 %x to i32
  %lshr = lshr i32 %zext, 15
  %trunc = trunc i32 %lshr to i16
  ret i16 %trunc
}

; Negative test

define i16 @lshr_16(i16 %x) {
; CHECK-LABEL: @lshr_16(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ZEXT]], 16
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[LSHR]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i16 %x to i32
  %lshr = lshr i32 %zext, 16
  %trunc = trunc i32 %lshr to i16
  ret i16 %trunc
}

; Negative test

define i16 @lshr_var_shift_amount(i8 %x, i8 %amt) {
; CHECK-LABEL: @lshr_var_shift_amount(
; CHECK-NEXT:    [[Z:%.*]] = zext i8 [[X:%.*]] to i32
; CHECK-NEXT:    [[ZA:%.*]] = zext i8 [[AMT:%.*]] to i32
; CHECK-NEXT:    [[S:%.*]] = lshr i32 [[Z]], [[ZA]]
; CHECK-NEXT:    [[A:%.*]] = add i32 [[S]], [[Z]]
; CHECK-NEXT:    [[S2:%.*]] = lshr i32 [[A]], 2
; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[S2]] to i16
; CHECK-NEXT:    ret i16 [[T]]
;
  %z = zext i8 %x to i32
  %za = zext i8 %amt to i32
  %s = lshr i32 %z, %za
  %a = add i32 %s, %z
  %s2 = lshr i32 %a, 2
  %t = trunc i32 %s2 to i16
  ret i16 %t
}

define i16 @lshr_var_bounded_shift_amount(i8 %x, i8 %amt) {
; CHECK-LABEL: @lshr_var_bounded_shift_amount(
; CHECK-NEXT:    [[Z:%.*]] = zext i8 [[X:%.*]] to i32
; CHECK-NEXT:    [[ZA:%.*]] = zext i8 [[AMT:%.*]] to i32
; CHECK-NEXT:    [[ZA2:%.*]] = and i32 [[ZA]], 15
; CHECK-NEXT:    [[S:%.*]] = lshr i32 [[Z]], [[ZA2]]
; CHECK-NEXT:    [[A:%.*]] = add i32 [[S]], [[Z]]
; CHECK-NEXT:    [[S2:%.*]] = lshr i32 [[A]], 2
; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[S2]] to i16
; CHECK-NEXT:    ret i16 [[T]]
;
  %z = zext i8 %x to i32
  %za = zext i8 %amt to i32
  %za2 = and i32 %za, 15
  %s = lshr i32 %z, %za2
  %a = add i32 %s, %z
  %s2 = lshr i32 %a, 2
  %t = trunc i32 %s2 to i16
  ret i16 %t
}

define void @lshr_big_dag(i16* %a, i8 %b, i8 %c) {
; CHECK-LABEL: @lshr_big_dag(
; CHECK-NEXT:    [[ZEXT1:%.*]] = zext i8 [[B:%.*]] to i32
; CHECK-NEXT:    [[ZEXT2:%.*]] = zext i8 [[C:%.*]] to i32
; CHECK-NEXT:    [[ADD1:%.*]] = add i32 [[ZEXT1]], [[ZEXT2]]
; CHECK-NEXT:    [[SFT1:%.*]] = and i32 [[ADD1]], 15
; CHECK-NEXT:    [[SHR1:%.*]] = lshr i32 [[ADD1]], [[SFT1]]
; CHECK-NEXT:    [[ADD2:%.*]] = add i32 [[ADD1]], [[SHR1]]
; CHECK-NEXT:    [[SFT2:%.*]] = and i32 [[ADD2]], 7
; CHECK-NEXT:    [[SHR2:%.*]] = lshr i32 [[ADD2]], [[SFT2]]
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[SHR2]] to i16
; CHECK-NEXT:    store i16 [[TRUNC]], i16* [[A:%.*]], align 2
; CHECK-NEXT:    ret void
;
  %zext1 = zext i8 %b to i32
  %zext2 = zext i8 %c to i32
  %add1 = add i32 %zext1, %zext2
  %sft1 = and i32 %add1, 15
  %shr1 = lshr i32 %add1, %sft1
  %add2 = add i32 %add1, %shr1
  %sft2 = and i32 %add2, 7
  %shr2 = lshr i32 %add2, %sft2
  %trunc = trunc i32 %shr2 to i16
  store i16 %trunc, i16* %a, align 2
  ret void
}

define <2 x i16> @lshr_vector(<2 x i8> %x) {
; CHECK-LABEL: @lshr_vector(
; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[ZA:%.*]] = and <2 x i32> [[Z]], <i32 7, i32 8>
; CHECK-NEXT:    [[S:%.*]] = lshr <2 x i32> [[Z]], [[ZA]]
; CHECK-NEXT:    [[A:%.*]] = add <2 x i32> [[S]], [[Z]]
; CHECK-NEXT:    [[S2:%.*]] = lshr <2 x i32> [[A]], <i32 4, i32 5>
; CHECK-NEXT:    [[T:%.*]] = trunc <2 x i32> [[S2]] to <2 x i16>
; CHECK-NEXT:    ret <2 x i16> [[T]]
;
  %z = zext <2 x i8> %x to <2 x i32>
  %za = and <2 x i32> %z, <i32 7, i32 8>
  %s = lshr <2 x i32> %z, %za
  %a = add <2 x i32> %s, %z
  %s2 = lshr <2 x i32> %a, <i32 4, i32 5>
  %t = trunc <2 x i32> %s2 to <2 x i16>
  ret <2 x i16> %t
}

; Negative test - can only fold to <2 x i16>, requiring new vector type

define <2 x i8> @lshr_vector_no_new_vector_type(<2 x i8> %x) {
; CHECK-LABEL: @lshr_vector_no_new_vector_type(
; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[ZA:%.*]] = and <2 x i32> [[Z]], <i32 7, i32 8>
; CHECK-NEXT:    [[S:%.*]] = lshr <2 x i32> [[Z]], [[ZA]]
; CHECK-NEXT:    [[A:%.*]] = add <2 x i32> [[S]], [[Z]]
; CHECK-NEXT:    [[S2:%.*]] = lshr <2 x i32> [[A]], <i32 4, i32 5>
; CHECK-NEXT:    [[T:%.*]] = trunc <2 x i32> [[S2]] to <2 x i8>
; CHECK-NEXT:    ret <2 x i8> [[T]]
;
  %z = zext <2 x i8> %x to <2 x i32>
  %za = and <2 x i32> %z, <i32 7, i32 8>
  %s = lshr <2 x i32> %z, %za
  %a = add <2 x i32> %s, %z
  %s2 = lshr <2 x i32> %a, <i32 4, i32 5>
  %t = trunc <2 x i32> %s2 to <2 x i8>
  ret <2 x i8> %t
}

; Negative test

define <2 x i16> @lshr_vector_large_shift_amount(<2 x i8> %x) {
; CHECK-LABEL: @lshr_vector_large_shift_amount(
; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[ZA:%.*]] = and <2 x i32> [[Z]], <i32 7, i32 8>
; CHECK-NEXT:    [[S:%.*]] = lshr <2 x i32> [[Z]], [[ZA]]
; CHECK-NEXT:    [[A:%.*]] = add <2 x i32> [[S]], [[Z]]
; CHECK-NEXT:    [[S2:%.*]] = lshr <2 x i32> [[A]], <i32 16, i32 5>
; CHECK-NEXT:    [[T:%.*]] = trunc <2 x i32> [[S2]] to <2 x i16>
; CHECK-NEXT:    ret <2 x i16> [[T]]
;
  %z = zext <2 x i8> %x to <2 x i32>
  %za = and <2 x i32> %z, <i32 7, i32 8>
  %s = lshr <2 x i32> %z, %za
  %a = add <2 x i32> %s, %z
  %s2 = lshr <2 x i32> %a, <i32 16, i32 5>
  %t = trunc <2 x i32> %s2 to <2 x i16>
  ret <2 x i16> %t
}

define i16 @lshr_exact(i16 %x) {
; CHECK-LABEL: @lshr_exact(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i32 [[ZEXT]], 15
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[LSHR]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i16 %x to i32
  %lshr = lshr exact i32 %zext, 15
  %trunc = trunc i32 %lshr to i16
  ret i16 %trunc
}

; Negative test

define i16 @ashr_negative(i16 %x) {
; CHECK-LABEL: @ashr_negative(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[ASHR:%.*]] = ashr i32 [[ZEXT]], 15
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ASHR]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i16 %x to i32
  %ashr = ashr i32 %zext, 15
  %trunc = trunc i32 %ashr to i16
  ret i16 %trunc
}

define i16 @ashr_positive(i16 %x) {
; CHECK-LABEL: @ashr_positive(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ZEXT]], 32767
; CHECK-NEXT:    [[ASHR:%.*]] = ashr i32 [[AND]], 15
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ASHR]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i16 %x to i32
  %and = and i32 %zext, 32767
  %ashr = ashr i32 %and, 15
  %trunc = trunc i32 %ashr to i16
  ret i16 %trunc
}

define i16 @ashr_exact(i16 %x) {
; CHECK-LABEL: @ashr_exact(
; CHECK-NEXT:    [[ZEXT:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ZEXT]], 32767
; CHECK-NEXT:    [[ASHR:%.*]] = ashr exact i32 [[AND]], 15
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ASHR]] to i16
; CHECK-NEXT:    ret i16 [[TRUNC]]
;
  %zext = zext i16 %x to i32
  %and = and i32 %zext, 32767
  %ashr = ashr exact i32 %and, 15
  %trunc = trunc i32 %ashr to i16
  ret i16 %trunc
}
